Recently, advertising over more interactive media has become popular. For example, as the number of people using the Internet has exploded, advertisers have come to appreciate and utilize media and services offered over the Internet as a potentially powerful way to advertise. Interactive advertising often provides opportunities for advertisers to target their advertisements (“ads”) to a more appropriate or receptive audience. In other words, targeted ads are more likely to be useful to end users since the ads may be relevant to a need inferred from some user activity (such as relevant to a user's search query to a search engine, relevant to content in a document requested by the user, and so forth), characteristic (e.g., demographics), or the like. For example, query keyword targeting has been used by search engines to deliver relevant ads. In this case, the advertising system may determine which of the eligible ads should actually be displayed to the user, a process which could be based on several different factors. For example, the advertising system can rely on the popularity of the ads, so that more popular ads are displayed more often. Alternatively, the advertising system can rely on a computerized bidding process based on what the advertisers have stated they are willing to pay, so that advertisers willing to pay more are more likely to have their ad displayed. In these cases, advertisers generally want to target their ads to users interested in what they are offering.